Zobrist Hash
集合をハッシュする。
要素の追加・削除、集合の一致判定を
$ O(1)
で計算できる。
集合の要素としてあり得るものに乱数を割り当てる。要素の総XORが集合のハッシュ。
集合に要素を追加することを、その要素に割り当てられた乱数をXORすることと定める。
要素の削除はもう一度XORをすればできる。差集合も集合同士をXORすれば求められる。
リファレンス
集合をハッシュする (Zobrist hashing) / tatyam